package me.mingshan.leetcode;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/move-zeroes/description/
 * <p>
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * <p>
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 示例 2:
 * <p>
 * 输入: nums = [0]
 * 输出: [0]
 *
 * @author hanjuntao
 * @date 2025/6/13 0013
 */
public class L_283_move_zeroes {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        // 1,0,0,3,12
        // 1,3,0,0,12
        // 1,3,12,0,0
        //moveZeroes2(nums);
        //System.out.println(Arrays.toString(nums));


        int[] nums2 = {1, 0, 1};
        moveZeroes2(nums2);
        //System.out.println(Arrays.toString(nums2));


        int[] nums3 = {1, 0};
        //moveZeroes2(nums3);
        System.out.println(Arrays.toString(nums3));
    }

    /**
     * 思路：
     * 1. 创建一个栈，将所有非0的元素入栈
     * 2. 然后数组末尾填充0
     *
     * @param nums
     */
    private static void moveZeroes2(int[] nums) {
        // 栈的大小
        int stackSize = 0;
        for (int x : nums) {
            if (x != 0) {
                // 把 x 入栈
                nums[stackSize] = x;
                stackSize++;
            }
        }

        // 填充0, 需要从stackSize开始填充，到数组末尾
        for (int i = stackSize; i < nums.length; i++) {
            nums[i] = 0;
        }
    }

    /**
     * 思路：
     * 1. 创建一个指针left ，指向第一个为0的元素位置
     * 2. 创建一个指针right ，指向第一个不为0的元素位置
     * 3. 交换left和right位置
     *
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }

        if (nums.length == 1) {
            return;
        }

        // 指向已经处理好的末尾下一个待插入位置
        int left = 0;
        // 待出库的元素
        int right = 1;

        for (right = 1; right < nums.length; right++) {
            // 如果left指向的元素为0，且right指向的元素不为0，则交换位置
            if (nums[left] == 0 && nums[right] != 0) {
                // 交换顺序
                nums[left] = nums[right];
                nums[right] = 0;
                left++;
            } else if (nums[left] != 0) {
                // left指向的元素不为0，则left++
                left++;
            }
        }

    }

}
